package LeetCode.leetcode;

/**
 * 两数相除 (不能使用除号)
 * @author: leiwenkang02@meituan.com
 * @date: 2018/9/28
 * @time: 10:26
 */
public class Test29两数相除 {
    public static void main(String[] args) {
        System.out.println(divide(-2147483648, -1));
    }
    public static int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return Integer.MAX_VALUE;
        }
        int sign = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            sign = -1;
        }
        long lividend = Math.abs((long)dividend);
        long livisor = Math.abs((long)divisor);

        long lans = ldivide(lividend, livisor);
        int result;
        if (lans > Integer.MAX_VALUE) {
            result = (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        } else {
            result = (int)(sign * lans);
        }
        return result;
    }

    private static long ldivide(long ldividend, long ldivisor) {
        //28   拆分成  3 * 2^2^2  + 3 + 1
        if (ldividend < ldivisor) {
            return 0;
        }
        long sum = ldivisor;
        long count = 1;
        while (sum + sum < ldividend) {
            sum += sum;    //3 * 2    3 * 2^2    3 * 2^2^2
            count += count;//    2        2^2        2^2^2
        }
        //count为8，此时sum = 24 ，还剩4，找出4除3能余几
        return count + ldivide(ldividend - sum, ldivisor);
    }
}
